package leetcode.od;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author pppppp
 * @date 2022/3/30 9:19
 * 第一行输入N，表示下面要输入多少个坐标
 * 往后的N行输入x y坐标，空格隔开。
 * 问，输入的N个坐标中能组成多少个正方形。
 * <p>
 * 输入
 * 3
 * 0 0
 * 1 2
 * 3 1
 * 输出
 * 0 （3个点一定构不成一个正方形）
 * <p>
 * 输入
 * 4
 * 0 0
 * 1 2
 * 3 1
 * 2 -1
 * 输出
 * 1
 */
public class 正方形个数 {
    @Test
    public void T_0() {
        int[][][] nums = {{{0, 0}, {1, 2}, {3, 1}}, {{0, 0}, {1, 2}, {3, 1}, {2, -1}}};
        int[] ans = {0, 1};
        for (int i = 1; i < nums.length; i++) {
            System.out.println(numOfSquare(nums[i]) == ans[i]);
        }
    }

    LinkedList<int[]> path = new LinkedList<>();
    List<List<int[]>> res = new ArrayList<>();

    int numOfSquare(int[][] nums) {
        if (nums.length < 4) {
            return 0;
        }
        /*回溯 + 判断是否为正方形*/
        dfs(0, nums);
        int cnt = 0;
        for (List<int[]> re : res) {
            if(isSquare(re)){
                cnt++;
            }
        }
        return cnt;
    }

    private boolean isSquare(List<int[]> list) {
        int[][] points = new int[4][2];
        points[0] = list.get(0);
        points[1] = list.get(1);
        points[2] = list.get(2);
        points[3] = list.get(3);

        for (int i = 0; i < 4; i++) {
            for (int j = i+1; j < 4; j++) {
                for (int k = j+1; k < 4; k++) {
                    int x1 = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]);
                    int y1 = (points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
                    int x2 = (points[k][0] - points[j][0]) * (points[k][0] - points[j][0]);
                    int y2 = (points[k][1] - points[j][1]) * (points[k][1] - points[j][1]);
                    if(x1 + y1 != x2 + y2 && x1 + y1 != 2*(x2 + y2) && 2*(x1 + y1) != x2 + y2){
                        return false;
                    }
                }
            }
        }
        return true;
    }

    private void dfs(int i, int[][] nums) {
        if(path.size() == 4){
            res.add(new ArrayList<>(path));
            return;
        }

        if (i == nums.length) {
            return;
        }

        for (int j = i; j < nums.length; j++) {
            path.add(nums[j]);
            dfs(j+1,nums);
            path.removeLast();
        }
    }
}
